# 翻转一棵二叉树。 
# 
#  示例： 
# 
#  输入： 
# 
#       4
#    /   \
#   2     7
#  / \   / \
# 1   3 6   9 
# 
#  输出： 
# 
#       4
#    /   \
#   7     2
#  / \   / \
# 9   6 3   1 
# 
#  备注: 
# 这个问题是受到 Max Howell 的 原问题 启发的 ： 
# 
#  谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。 
#  Related Topics 树 
#  👍 831 👎 0


from typing import List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return root
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left = right
        root.right = left
        return root


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 广度优先遍历, 打印树
def log_tree(r: TreeNode):
    if r is None:
        return
    stack = [r]
    while stack:
        node = stack.pop(0)
        log(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)


def tree_list(r: TreeNode) -> List[int]:
    if r is None:
        return []
    ans = []
    q = [r]
    while q:
        node = q.pop(0)
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return ans





"""
递归, 如果左子树和右子树都已经反转
那么交换左右子树即可
"""

# def invertTree(self, root: TreeNode) -> TreeNode:
#     if root is None:
#         return root
#     left = self.invertTree(root.left)
#     right = self.invertTree(root.right)
#     root.left = right
#     root.right = left
#     return root

if __name__ == '__main__':
    s = Solution()
    #       4
    #    /   \
    #   2     7
    #  / \   / \
    # 1   3 6   9
    root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7, TreeNode(6), TreeNode(9)))
    new_tree = s.invertTree(root)
    assert tree_list(new_tree) == [4, 7, 2, 9, 6, 3, 1], tree_list(new_tree)
